module pflanza.lsystem;

import std.conv;
import std.math;
import stream = std.stream;
import std.string;
import std.stdio;
import std.ctype;
import std.boxer;
import rand = utils.mt19937ar;

enum TokenType {
    invalid,
    eof, //end of file
    id,
    number,
    comma, // ,
    rule, // ->
    condition, // :
    bracket_open, // (
    bracket_close, // )
    /*
    poly_open, // {   //becomes POLYOPEN
    poly_close, // }  //becomes POLYCLOSE
    */
    state_push, // [
    state_pop, // ]
    assign, // =
    cmp_eq, // ==
    sub, //-
    add, //plus
    mul, //*
    div, // /
    pow, // ^
    cmp_g, //>
    cmp_ge, //>=
    cmp_l, //<
    cmp_le, //<=
    and, // &
    or, // |
    semi, // ;
    expr, // $
    inv, // !
}

enum RuleItemType {
    invalid,
    non_terminal,
    expression,
    callback,
    state_push,
    state_pop,
}

private struct TokenToParamRule {
    TokenType token;
    RuleItemType rule;
}

private const TokenToParamRule[] gTokenToParamRule = [
    {TokenType.state_push, RuleItemType.state_push},
    {TokenType.state_pop, RuleItemType.state_pop},
];

public struct Token {
    TokenType type;
    char[] data;
    float number;

    char[] toString() {
        if (type == TokenType.id) {
            return "id=" ~ data;
        } else if (type == TokenType.number) {
            return "num=" ~ std.string.toString(number);
        }
        return std.string.toString(cast(uint)type);
    }
}

private struct RuleItem {
    //simple and stupid
    RuleItemType rule;
    Expression[] expr;
    RuleSet rule_ref;
    char[] rule_name; //needed for forward references
    void delegate(char[] name, float[] values) callback; //for RuleItemType.callback
    char[] callback_name;
}

//naive Stack template because D stdlib doesn't provide one
private class Stack(T) {
    private T[] mData;

    void push(T t) {
        mData ~= t;
    }
    T pop() {
        T res = top();
        mData = mData[0..$-1];
        return res;
    }
    bool empty() {
        return mData.length == 0;
    }
    T top() {
        return mData[$-1];
    }
    void top(T t) {
        mData[$-1] = t;
    }
    void clear() {
        mData = null;
    }
}

private class ScanError: Exception {
        this(char[] msg) {
            super(msg);
        }
    }

public class ParseError: Exception {
        this(char[] msg) {
            super(msg);
        }
    }

public class VariableScope {
    private {
        struct State {
            float[char[]] vars;
            Box userdata;
        }

        Stack!(State) mStateStack;
        Stack!(float[char[]]) mFunctionStack;
    }

    private float* resolve(char[] name) {
        float* pf = name in mFunctionStack.top;
        if (!pf) {
            pf = name in mStateStack.top.vars;
        }
        return pf;
    }

    this() {
        mStateStack = new Stack!(State)();
        mFunctionStack = new Stack!(float[char[]])();
        reset();
    }

    void reset() {
        mStateStack.clear();
        mFunctionStack.clear();

        State nstate;
        mStateStack.push(nstate);
        //empty frame to simplify readVar
        mFunctionStack.push(null);
    }

    //warning: semantics depend from current recursion stack
    // also note, that push/pop of state/function can be intermixed
    float readVar(char[] name) {
        float* pf = resolve(name);
        if (!pf)
            throw new Exception("var not found: " ~ name);
        return *pf;
    }
    void setVar(char[] name, float val) {
        float* pf = resolve(name);
        if (!pf) {
            //create on assign

            State s = mStateStack.top;
            s.vars[name] = val;
            mStateStack.top = s;

            //writefln("set: %s=%s", name, val);
            pf = resolve(name);
        }
        assert(pf);
        *pf = val;
    }

    Box userdata_state() {
        return mStateStack.top.userdata;
    }
    void userdata_state(Box b) {
        auto s = mStateStack.top;
        s.userdata = b;
        mStateStack.top = s;
    }

    void push_state() {
        //debug writefln("push_state");
        State nstate;
        State cstate = mStateStack.top;
        //the variables must be copied... sucks
        foreach (char[] key, float val; cstate.vars) {
            nstate.vars[key] = val;
        }
        nstate.userdata = cstate.userdata;
        mStateStack.push(nstate);
    }
    void pop_state() {
        //debug writefln("pop_state");
        mStateStack.pop();
    }

    void push_function(float[char[]] params) {
        //debug writefln("push_function");
        mFunctionStack.push(params);
    }
    void pop_function() {
        //debug writefln("pop_function");
        mFunctionStack.pop();
    }
}

//too lazy for typing
alias VariableScope EvalContext;

public class Expression {
    public abstract float calc(EvalContext ctx);
    public void delegate(float set) getLValue(EvalContext ctx) {
        throw new Exception("no L-value");
    }

    static float boolToFloat(bool b) { return b ? +1 : -1; }
    static bool floatToBool(float f) { return f >= 0; }
}

enum BinOpType {
    Add,
    Sub,
    Mul,
    Div,
    Pow,
    And,
    Or,
    CmpEQ,
    CmpL,
    CmpLE,
    CmpG,
    CmpGE,
    Assign,
    Comma,
}

public class ExprBinOp : Expression {
    BinOpType op;
    Expression e1, e2;

    public this(Expression e1, Expression e2, BinOpType op) {
        this.e1 = e1;
        this.e2 = e2;
        this.op = op;
    }

    public float calc(EvalContext ctx) {
        if (op == BinOpType.Assign) {
            auto foo = e1.getLValue(ctx);
            auto x = e2.calc(ctx);
            foo(x);
            return x;
        } else {
            float v1 = e1.calc(ctx);
            float v2 = e2.calc(ctx);
            switch (op) {
                case BinOpType.Add: return v1+v2;
                case BinOpType.Sub: return v1-v2;
                case BinOpType.Mul: return v1*v2;
                case BinOpType.Div: return v1/v2;
                case BinOpType.Pow: return pow(v1, v2);
                case BinOpType.And: return boolToFloat(floatToBool(v1) && floatToBool(v2));
                case BinOpType.Or: return boolToFloat(floatToBool(v1) || floatToBool(v2));
                case BinOpType.CmpEQ: return boolToFloat(v1 == v2); //xxx: epsilon
                case BinOpType.CmpL: return boolToFloat(v1 < v2);
                case BinOpType.CmpLE: return boolToFloat(v1 <= v2);
                case BinOpType.CmpG: return boolToFloat(v1 > v2);
                case BinOpType.CmpGE: return boolToFloat(v1 >= v2);
                //evaluate v1 and v2, but the last one makes the value
                case BinOpType.Comma: return v2;
                default:
                    assert(false);
            }
        }
        assert(false);
    }

    public char[] toString() {
        char[][BinOpType] foo;
        foo[BinOpType.Add] = "+";
        foo[BinOpType.Sub] = "-";
        foo[BinOpType.Mul] = "*";
        foo[BinOpType.Div] = "/";
        foo[BinOpType.Pow] = "^";
        foo[BinOpType.And] = "&";
        foo[BinOpType.Or] = "|";
        foo[BinOpType.CmpEQ] = "==";
        foo[BinOpType.CmpL] = "<";
        foo[BinOpType.CmpLE] = "<=";
        foo[BinOpType.CmpG] = ">";
        foo[BinOpType.CmpGE] = ">=";
        foo[BinOpType.Comma] = ";";
        foo[BinOpType.Assign] = "=";
        return "("~e1.toString()~foo[op]~e2.toString()~")";
    }
}

enum UnOpType {
    Neg,
    Inv,
}

public class ExprUnary : Expression {
    UnOpType op;
    Expression e;

    public this(Expression e, UnOpType op) {
        this.op = op;
        this.e = e;
    }

    public float calc(EvalContext ctx) {
        float v = e.calc(ctx);
        switch (op) {
            case UnOpType.Neg: return -v;
            case UnOpType.Inv: return boolToFloat(!floatToBool(v));
            default:
                assert(false);
        }
    }
}

public class ExprConst : Expression {
    float value;
    public float calc(EvalContext ctx) {
        return value;
    }
    public this(float val) {
        value = val;
    }
    public char[] toString() {
        return std.string.toString(value);
    }
}

public class ExprVar : Expression {
    char[] name;
    EvalContext tmp;

    public float calc(EvalContext ctx) {
        return ctx.readVar(name);
    }
    public this(char[] name) {
        this.name = name;
    }
    public void setValue(float set) {
        tmp.setVar(name, set);
    }
    public void delegate(float set) getLValue(EvalContext ctx) {
        tmp = ctx; //infinitely unclean!
        return &setValue;
    }
    public char[] toString() {
        return name;
    }
}

alias float delegate(char[] name, float[] params) FunctionDelegate;

public struct Function {
    int param_count;
    FunctionDelegate func;

    public static Function opCall(int param_count, FunctionDelegate func) {
        Function ret;
        ret.param_count = param_count;
        ret.func = func;
        return ret;
    }
}

public class ExprFuncCall : Expression {
    char[] name;
    float delegate(char[] name, float[] params) func;
    Expression[] params;

    public float calc(EvalContext ctx) {
        float[] vParams = new float[params.length];
        for (int i = 0; i < params.length; i++) {
            vParams[i] = params[i].calc(ctx);
        }
        return func(name,vParams);
    }

    public this(char[] name, float delegate(char[] name, float[] params) func, Expression[] params) {
        this.name = name;
        this.func = func;
        this.params = params[];
    }

    public char[] toString() {
        //no output of parameters...
        return name ~ "()";
    }
}

public class Rule {
    Expression prob;
    Expression condition;
    RuleItem[] replacement;
    RuleSet set;

    public this(RuleSet set, Expression prob, Expression condition, RuleItem[] replacement) {
        this.set = set;
        this.prob = prob;
        this.condition = condition;
        this.replacement = replacement;
    }
}

public class RuleSet {
    char[][] params;   //for "efficiency" :-)
    char[] nonterminal;
    Rule[] repl;

    public this(char[] nonterminal, char[][] params) {
        this.nonterminal = nonterminal;
        this.params = params;
    }

    public char[] toString() {
        /*char[] probs = "(";
        foreach (Rule r; repl) {
            probs ~= std.string.toString(r.prob) ~ ",";
        }
        probs ~= ")";
        return nonterminal ~ " " ~ probs;*/
        return "out of order, don't use";
    }
}

public class LSystemParser {
    private {
        RuleSet[char[]] mRules;
        Rule[] mAllRules;
        VariableScope mVars;
        RuleSet mInitRuleRef;
        Expression[] mInitVars;
        void delegate()[] mOnPushState;
        Function[char[]] mRegisteredFuncs;
    }

    public VariableScope vars() {
        return mVars;
    }

    //if current token is "(", then parse list of parameters: (<expr>{,<expr>}*)
    private Expression[] parseOptParams(Tokenizer tok) {
        Expression[] params;
        if (tok.tryEat(TokenType.bracket_open)) {
            if (!tok.tryEat(TokenType.bracket_close)) {
                for (;;) {
                    params ~= parseExpression(tok);
                    if (!tok.tryEat(TokenType.comma)) {
                        tok.mustEat(TokenType.bracket_close, ") expected");
                        break;
                    }
                }
            }
        }
        return params;
    }

    private void parseLine(char[] line) {
        Tokenizer tok = new Tokenizer();
        tok.resetScanner(line);

        try {
            if (tok.tryEat(TokenType.expr)) {
                Expression e = parseExpression(tok);
                mInitVars ~= e;
                tok.mustEat(TokenType.eof, "end of line expected");
            } else {
                parseRule(tok);
            }
        } catch (ScanError e) {
            throw new ParseError("Scan error at " ~ std.string.toString(tok.pos) ~ ": " ~ e.msg);
        }
    }
    private Rule parseRule(Tokenizer tok) {
        char[] name;
        char[][] params;

        name = tok.mustEatID("rule name expected");

        if (tok.tryEat(TokenType.bracket_open)) {
            while (true) {
                char[] param;
                if (tok.tryEatID(param)) {
                    params ~= param;
                }
                if (!tok.tryEat(TokenType.comma)) {
                    tok.mustEat(TokenType.bracket_close, ") expected");
                    break;
                }
            }
        }

        //condition expression is optional!
        Expression prob = parseExpression(tok, false);

        //warning: dirty hack
        uint condStart = tok.pos;
        uint lastPos = condStart;
        Expression condition;
        if (tok.tryEat(TokenType.condition)) {
            condition = parseExpression(tok);
        }

        tok.mustEat(TokenType.rule, "rule expected");

        //parse ruledata itsself
        RuleItem[] ruledata;

        while (tok.type != TokenType.eof) {
            RuleItemType t = RuleItemType.invalid;
            foreach (TokenToParamRule bla; gTokenToParamRule) {
                if (bla.token == tok.type) {
                    t = bla.rule;
                    break;
                }
            }

            char[] tmp;

            if (t != RuleItemType.invalid)  {
                //some action, with parameter?
                tok.nextToken();
                RuleItem r;
                r.rule = t;
                r.expr = parseOptParams(tok);
                ruledata ~= r;
                if (r.expr.length > 1) {
                    throw new ParseError("0 or 1 params expected");
                }
            } else if (tok.tryEat(TokenType.expr)) {
                //evaluate expression :-)
                RuleItem r;
                r.rule = RuleItemType.expression;
                r.expr = [parseExpression(tok)];
                ruledata ~= r;
            } else if (tok.tryEatID(tmp)) {
                //take this as non-terminal "invocation"
                RuleItem r;
                r.rule_name = tmp;
                r.rule = RuleItemType.non_terminal;
                r.expr = parseOptParams(tok);
                ruledata ~= r;
            } else {
                throw new ParseError("stfu: "~std.string.toString(cast(int)(tok.type)));
            }
        }

        addRule(name, params, prob, condition, ruledata);

//        debug writefln("added rule %s: >%s< >%s<", name, prob, condition);
        return null;

    }

    private void addRule(char[] name, char[][] params, Expression prob,
        Expression condition, RuleItem[] ruledata)
    {
        RuleSet rs;
        if (!(name in mRules)) {
            rs = new RuleSet(name, params);
            mRules[name] = rs;
        }
        rs = mRules[name];
        if (rs.params.length != params.length) {
            throw new Exception("expected "~std.string.toString(rs.params.length)~" params, but got "
                ~std.string.toString(params.length)~" params");
        }
        //parameter names must be equal
        for (uint n = 0; n < params.length; n++) {
            if (rs.params[n] != params[n]) {
                throw new Exception("rule >" ~ name ~ "<: param names not all teh same!");
            }
        }
        Rule r = new Rule(rs, prob, condition, ruledata);
        rs.repl ~= r;
        mAllRules ~= r;
    }

    //register a command, that looks like a non-terminal
    //I'm really REALLY REALLLLY sorry for the following code
    //(I create a single rule for each function call, unifies name resolution)
    public void registerCommand(char[] name, int param_count,
        void delegate(char[] name, float[] values) command)
    {
        RuleItem r;
        r.rule = RuleItemType.callback;
        r.callback = command;
        r.callback_name = name;
        char[][] params; //this has no meaning except for count of params
        params.length = param_count;
        addRule(name, params, new ExprConst(1.0f), null, [r]);
    }

    public void registerFunction(char[] name, int param_count,
        FunctionDelegate func)
    {
        Function f = Function(param_count, func);
        mRegisteredFuncs[name] = f;
    }

    public void registerOnPush(void delegate() onpush) {
        mOnPushState ~= onpush;
    }

    //resolve the non-terminal names (can't be done while parsing because of
    // forward references)
    private void fixupRules() {
        foreach (Rule r; mAllRules) {
            foreach (inout RuleItem ri; r.replacement) {
                if (ri.rule == RuleItemType.non_terminal) {
                    RuleSet* prs = ri.rule_name in mRules;
                    if (!prs) {
                        throw new Exception("rule not found: >"~ri.rule_name~"<");
                    }
                    RuleSet rs = *prs;
                    if (rs.params.length != ri.expr.length) {
                        throw new Exception("Rule "~ rs.nonterminal ~": wrong param. count");
                    }
                    ri.rule_ref = rs;
                }
            }
        }
    }

    public Expression parseExpression(Tokenizer tok, bool must = true) {
        struct Operator {
            BinOpType op;
            TokenType token;
            int prec;
        }

        static Operator[] ops = [
            {BinOpType.Comma, TokenType.semi, -4},
            {BinOpType.Assign, TokenType.assign, -3},
            {BinOpType.And, TokenType.and, -2},
            {BinOpType.Or, TokenType.or, -2},
            {BinOpType.CmpL, TokenType.cmp_l, -1},
            {BinOpType.CmpLE, TokenType.cmp_le, -1},
            {BinOpType.CmpG, TokenType.cmp_g, -1},
            {BinOpType.CmpGE, TokenType.cmp_ge, -1},
            {BinOpType.CmpEQ, TokenType.cmp_eq, -1},
            {BinOpType.Add, TokenType.add, 0},
            {BinOpType.Sub, TokenType.sub, 0},
            {BinOpType.Mul, TokenType.mul, 1},
            {BinOpType.Div, TokenType.div, 1},
            {BinOpType.Pow, TokenType.pow, 2},
        ];
        static Operator[TokenType] optable;
        static bool didinit;
        static int minprec = int.max, maxprec = int.min;

        if (!didinit) {
            foreach(Operator op; ops) {
                optable[op.token] = op;
                if (op.prec < minprec)
                    minprec = op.prec;
                if (op.prec > maxprec)
                    maxprec = op.prec;
            }
            didinit = true;
        }

        Expression delegate(int prec, bool must = true) parseExpr;

        Expression parseT(bool must) {
            //also do () and some unary operators
            if (tok.tryEat(TokenType.bracket_open)) {
                auto e = parseExpr(minprec);
                tok.mustEat(TokenType.bracket_close, ") expected");
                return e;
            } else if (tok.tryEat(TokenType.sub)) {
                return new ExprUnary(parseT(true), UnOpType.Neg);
            } else if (tok.tryEat(TokenType.inv)) {
                return new ExprUnary(parseT(true), UnOpType.Inv);
            } else if (tok.type == TokenType.id) {
                char[] id_name = tok.mustEatID("bla");
                if (tok.type == TokenType.bracket_open) {
                    //function call
                    Expression[] parExprs = parseOptParams(tok);
                    if (id_name in mRegisteredFuncs) {
                        Function func = mRegisteredFuncs[id_name];
                        if (func.param_count == parExprs.length)
                            return new ExprFuncCall(id_name,func.func,parExprs);
                        else
                            throw new ParseError("Function "~id_name~" expects "~std.string.toString(func.param_count)~" parameters");
                    } else
                        throw new ParseError("Function "~id_name~" not found");
                } else
                    //variable
                    return new ExprVar(id_name);
            } else if (tok.type == TokenType.number) {
                return new ExprConst(tok.mustEatNumber("blo"));
            }
            if (must) {
                throw new ParseError("?");
            }
            return null;
        }
        Expression parseExprB(int prec, bool must = true) {
            Expression e;
            if (prec <= maxprec) {
                e = parseExpr(prec+1, must);
            } else {
                return parseT(must);
            }

            if (!e)
                return null;

            Operator* op = tok.type in optable;

            if (op && prec == op.prec) {
                tok.mustEat(op.token, "ICE");
                //if an assign follows, make it like in C:
                // i.e. e1 + = e2 => e1 = e1 + e2
                if (tok.tryEat(TokenType.assign)) {
                    auto e2 = new ExprBinOp(e, parseExpr(prec), op.op);
                    return new ExprBinOp(e, e2, BinOpType.Assign);
                } else {
                    return new ExprBinOp(e, parseExpr(prec), op.op);
                }
            }

            return e;
        }

        parseExpr = &parseExprB;

        return parseExpr(minprec, must);
    }

    public bool setRules(stream.Stream ruleFile) {
        return addRules(ruleFile.toString());
    }

    public bool addRules(char[] rules) {
        //clear(); don't clear, registerCommand() adds internal rules
        bool ret = true;
        char[][] ruleLines = splitlines(rules);
        foreach (int n, char[] line; ruleLines) {
            try {
                if (line.length > 0 && line[0] != '#')
                    parseLine(line);
            } catch (ParseError e) {
                writefln("Error on line %d: %s",n+1,e.msg);
                ret = false;
            }
        }
        /*debug foreach (RuleSet r; mRules) {
            writefln("%s",r);
        }*/
        return ret;
    }

    //for recursion of non-terminals
    struct RuleContext {
        float[char[]] params;
    }

    public this() {
        clear();
    }


    public void clear() {
        mInitRuleRef = new RuleSet("S", null);
        mRules = null;
        mRules[mInitRuleRef.nonterminal] = mInitRuleRef;
        mVars = new VariableScope();
    }

    //if you call start() multiple times, use this to reset the variables state
    public void reset() {
        mVars.reset();
    }

    //evaluate L-systems (from here, the registered callbacks will be called)
    public void start() {
        fixupRules(); //bind any unresolved rules

        foreach (Expression e; mInitVars) {
            e.calc(mVars); //establish side effects
        }
        execRule(mInitRuleRef, null);
    }

    //may return null!
    //also tests the condition
    //NOTE: current function parameters _must_ be on the "stack"
    private Rule pickRule(RuleSet rules) {
        //pick a rule; rules that aren't executed (condition) are no candidates
        //conditions are expressions, precalculate them (poor GC!)
        float probs[];
        probs.length = rules.repl.length;
        float prob_sum = 0;
        foreach (int i, Rule r; rules.repl) {
            float prob = 0;

            if (!r.condition || Expression.floatToBool(r.condition.calc(mVars))) {
                prob = r.prob ? r.prob.calc(mVars) : 1.0f;
            }

            probs[i] = prob;
            prob_sum += prob;
        }

        float pick = rand.genrand_real1()*prob_sum;
        Rule picked;
        foreach (int i, Rule r; rules.repl) {
            pick -= probs[i];
            if (pick < 0) {
                picked = r;
                break;
            }
        }
        return picked;
    }

    private void execRule(RuleSet rules, float[] params) {
        assert(params.length == rules.params.length);

        //establish local context
        //NOTE: this sucks
        float[char[]] context;
        for (uint n = 0; n < params.length; n++) {
            context[rules.params[n]] = params[n];
        }

        mVars.push_function(context);

        //pick a rule
        Rule rule = pickRule(rules);

        if (rule) {
            foreach (inout RuleItem r; rule.replacement) {
                switch (r.rule) {
                    case RuleItemType.callback: {
                        r.callback(r.callback_name, params);
                        break;
                    }
                    case RuleItemType.expression: {
                        foreach (Expression e; r.expr) {
                            e.calc(mVars); //execute for sideeffects
                        }
                        break;
                    }
                    case RuleItemType.state_pop: {
                        mVars.pop_state();
                        break;
                    }
                    case RuleItemType.state_push: {
                        mVars.push_state();
                        foreach (p; mOnPushState) {
                            p();
                        }
                        break;
                    }
                    case RuleItemType.non_terminal: {
                        float[] new_params;
                        //evaluate params
                        new_params.length = r.rule_ref.params.length;
                        for (uint n = 0; n < new_params.length; n++) {
                            new_params[n] = r.expr[n].calc(mVars);
                        }
                        //
                        execRule(r.rule_ref, new_params);
                        break;
                    }
                    default:
                        assert(false);
                }
            }
        }

        mVars.pop_function();
    }
}

public class Tokenizer {
    private {
        uint mTokenPos;
        Token mCurrent;
        Token[] mTokens;
    }

    TokenType type() {
        return mCurrent.type;
    }

    public uint pos() {
        return mTokenPos;
    }

    public this(Token[] tokens) {
        tokens = tokens;
    }
    public this() {
    }

    public void resetScanner(char[] str) {
        mTokens = tokenize(str);
        mTokenPos = 0;
        nextToken();
    }

    public void nextToken() {
        if (mTokenPos < mTokens.length) {
            mCurrent = mTokens[mTokenPos];
            mTokenPos++;
        } else {
            mCurrent = Token.init;
            mCurrent.type = TokenType.eof;
        }
    }

    public bool tryEat(TokenType token) {
        if (mCurrent.type == token) {
            nextToken();
            return true;
        }
        return false;
    }
    public bool tryEatID(out char[] data) {
        if (mCurrent.type == TokenType.id) {
            data = mCurrent.data;
            nextToken();
            return true;
        }
        return false;
    }
    public bool tryEatNumber(out float number) {
        if (mCurrent.type == TokenType.number) {
            number = mCurrent.number;
            nextToken();
            return true;
        }
        return false;
    }
    public void mustEat(TokenType token, char[] err) {
        if (mCurrent.type == token) {
            nextToken();
        } else {
            throw new ScanError("Token "~std.string.toString(cast(int)mCurrent.type)~" found, but: "~err);
        }
    }
    public char[] mustEatID(char[] err) {
        char[] id;
        if (!tryEatID(id)) {
            mustEat(TokenType.id, err);
        }
        return id;
    }
    public float mustEatNumber(char[] err) {
        float number;
        if (!tryEatNumber(number)) {
            mustEat(TokenType.number, err);
        }
        return number;
    }
}

private Token[] tokenize(char[] str) {
    char[] mData;
    TokenType mCurrent;
    char[] mCurrentData;
    uint mPos;

    char[] scanNum() {
        auto n = mPos;
        while (n < mData.length && isdigit(mData[n]))
            n++;
        auto res = mData[mPos .. n];
        mPos = n;
        return res;
    }

    TokenType scan() {
    again:
        mCurrentData = null;
        if (mPos >= mData.length) {
            mCurrent = TokenType.eof;
        } else {
            mCurrent = TokenType.invalid;
            char next;
            if (mPos+1<mData.length)
                next = mData[mPos+1];
            switch (mData[mPos]) {
                case '-': {
                    if (next == '>') {
                        mCurrent = TokenType.rule;
                        mPos++;
                    } else {
                        mCurrent = TokenType.sub;
                    }
                    break;
                }
                case '<': {
                    if (next == '=') {
                        mCurrent = TokenType.cmp_le;
                        mPos++;
                    } else {
                        mCurrent = TokenType.cmp_l;
                    }
                    break;
                }
                case '>': {
                    if (next == '=') {
                        mCurrent = TokenType.cmp_ge;
                        mPos++;
                    } else {
                        mCurrent = TokenType.cmp_g;
                    }
                    break;
                }
                case '=': {
                    if (next == '=') {
                        mCurrent = TokenType.cmp_eq;
                        mPos++;
                    } else {
                        mCurrent = TokenType.assign;
                    }
                    break;
                }
                case ':': mCurrent = TokenType.condition; break;
                case ';': mCurrent = TokenType.semi; break;
                case '(': mCurrent = TokenType.bracket_open; break;
                case ')': mCurrent = TokenType.bracket_close; break;
                case '{': {
                    mCurrent = TokenType.id;
                    mCurrentData = "POLYOPEN";
                    break;
                }
                case '}': {
                    mCurrent = TokenType.id;
                    mCurrentData = "POLYCLOSE";
                    break;
                }
                case '.': {
                    mCurrent = TokenType.id;
                    mCurrentData = "POLYPOINT";
                    break;
                }
                case '[': mCurrent = TokenType.state_push; break;
                case ']': mCurrent = TokenType.state_pop; break;
                case '+': mCurrent = TokenType.add; break;
                case '*': mCurrent = TokenType.mul; break;
                case '/': mCurrent = TokenType.div; break;
                case ',': mCurrent = TokenType.comma; break;
                case '^': mCurrent = TokenType.pow; break;
                case '&': mCurrent = TokenType.and; break;
                case '$': mCurrent = TokenType.expr; break;
                case '!': mCurrent = TokenType.inv; break;
                case '|': mCurrent = TokenType.or; break;
                case ' ': mPos++; goto again; //:-)
                default:
            }
            if (mCurrent != TokenType.invalid) {
                mPos++;
            } else {
                //id?
                if (isalpha(mData[mPos])) {
                    auto n = mPos + 1;
                    while (n < mData.length && (isalpha(mData[n]) || isdigit(mData[n]) || mData[n] == '_')) {
                        n++;
                    }
                    mCurrent = TokenType.id;
                    mCurrentData = mData[mPos .. n];
                    mPos = n;
                } else {
                    //try number
                    auto start = mPos;
                    char[] num = scanNum();
                    if (num.length > 0) {
                        if (mPos < mData.length && mData[mPos] == '.') {
                            mPos++;
                            char[] num2 = scanNum();
                            if (num2.length == 0) {
                                throw new Exception("no number");
                            }
                        }
                    }
                    mCurrentData = mData[start .. mPos];
                    mCurrent = TokenType.number;
                }
            }
        }
        if (mCurrent == TokenType.invalid) {
            throw new Exception("Unlexable char: >" ~ mData[mPos..mPos+1] ~ "< at "~std.string.toString(mPos));
        }
        return mCurrent;
    }

    //pre-tokenize everything
    mCurrent = TokenType.invalid;
    mPos = 0;
    mCurrentData = null;
    mData = str;

    Token[] res;
    Token tok;
    do {
        scan();
        tok.type = mCurrent;
        tok.data = mCurrentData;
        if (tok.type == TokenType.number) {
            tok.number = toFloat(tok.data);
        }
        res ~= tok;
    } while (tok.type != TokenType.invalid && tok.type != TokenType.eof);
    return res;
}

unittest {
    class Test {
        char[] mName;
        float[] mVals;
        int mCount;

        void run() {
            auto l = new LSystemParser();
            //l.setRules("test(0.34): f[sdff]F(0.123)\n");
            l.registerCommand("A", 1, &foo);
            l.addRules("$n=5");
            l.addRules("S -> X(6, 1)");
            l.addRules("X(a, b) 4+7*65 :  a > 0 -> X(a-1, b*a)");
            l.addRules("X(a, b) 5 : a == 0 -> A(--b)");

            mCount = 0;
            l.start();
            assert(mName == "A");
            assert(mCount == 1);
            assert(mVals.length == 1);
            assert(mVals[0] == 720);

            Tokenizer tok = new Tokenizer();
            //tok.resetScanner("4^2*5+1 == 82;n=6;3");
            tok.resetScanner("2*(3-1)");
            Expression e = l.parseExpression(tok);
            assert(e.toString() == "(2*(3-1)");
            assert(e.calc(null) == 4.0f);
        }


        void foo(char[] name, float[] vals) {
            //writefln("call >%s< with %s", name, vals);
            mCount++;
            mName = name;
            mVals = vals;
        }
    }

    auto t = new Test();
    t.run();
}
